package code_rhapsody.hash_map;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Synhard
 * @version 1.0
 * @class Code3
 * @description 49. 字母异位词分组
 * 给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。
 *
 * 字母异位词指字母相同，但排列不同的字符串。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 * 示例 2:
 *
 * 输入: strs = [""]
 * 输出: [[""]]
 * 示例 3:
 *
 * 输入: strs = ["a"]
 * 输出: [["a"]]
 *  
 *
 * 提示：
 *
 * 1 <= strs.length <= 104
 * 0 <= strs[i].length <= 100
 * strs[i] 仅包含小写字母
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-27 8:05
 */
public class Code3 {
    public static void main(String[] args) {
        System.out.println(groupAnagrams(new String[]{"", "b", ""}));
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        Code3DSU unionFind = new Code3DSU(strs.length);
        for (int i = 0; i < strs.length; i++) {
            for (int j = i + 1; j < strs.length; j++) {
                if (check(strs[i], strs[j])) {
                    unionFind.union(i, j);
                }
            }
        }
        List<List<String>> res = new ArrayList<>();
        Map<Integer, List<String>> map = new HashMap<>(unionFind.getGroup());
        for (int i = 0; i < unionFind.parent.length; i++) {
            List<String> tmp = map.getOrDefault(unionFind.parent[i], new ArrayList<>());
            tmp.add(strs[i]);
            map.putIfAbsent(unionFind.parent[i], tmp);
        }

        for (Map.Entry<Integer, List<String>> e : map.entrySet()) {
            res.add(e.getValue());
        }

        return res;
    }

    private static boolean check(String s, String p) {
        if(s.length() != p.length()) {
            return false;
        }
        int[] count = new int[26];
        for(int i = 0; i < p.length(); i ++) {
            count[s.charAt(i) - 'a'] ++;
            count[p.charAt(i) - 'a'] --;
        }

        for(int i : count) {
            if(i != 0) {
                return false;
            }
        }
        return true;
    }
}

class Code3DSU {
    public int[] parent;
    public int[] size;
    public int group;

    public Code3DSU(int n) {
        this.group = n;
        this.parent = new int[n];
        this.size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (size[pRoot] >= size[qRoot]) {
            parent[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        } else {
            parent[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        }
        group--;
    }

    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public int getGroup() {
        return group;
    }
}